// 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

// 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

// L   C   I   R
// E T O E S I I G
// E   D   H   N
// 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

// 请你实现这个将字符串进行指定行数变换的函数：

// string convert(string s, int numRows);
// 示例 1:

// 输入: s = "LEETCODEISHIRING", numRows = 3
// 输出: "LCIRETOESIIGEDHN"
// 示例 2:

// 输入: s = "LEETCODEISHIRING", numRows = 4
// 输出: "LDREOEIIECIHNTSG"
// 解释:

// L     D     R
// E   O E   I I
// E C   I H   N
// T     S     G

#include <string>
#include <vector>

using namespace std;

// 利用二维矩阵模拟
class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length();
        if (numRows == 1 || numRows >= n) {
            return s;
        }
        int t = numRows * 2 - 2; // 在矩阵上填写字符时，会向下填写 r 个字符，然后向右上继续填写 r−2 个字符，最后回到第一行，因此 Z 字形变换的周期 t=r+r−2=2r−2
        int numCols = (n + t - 1) / t * (numRows - 1);
        vector<string> mat(numRows, string(numCols, 0));
        int x = 0;
        int y = 0;
        for (int i = 0; i < n; ++i) {
            mat[x][y] = s[i];
            if (i % t < numRows - 1) {
                ++x; // 向下移动
            } else {
                --x;
                ++y; // 向右上移动
            }
        }
        string res;
        for (auto &row : mat) {
            for (char c : row) {
                if (c) {
                    res += c;
                }
            }
        }
        return res;
    }
};

// 压缩矩阵空间
class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length();
        if (numRows == 1 || numRows >= n) {
            return s;
        }
        vector<string> mat(numRows);
        int x = 0;
        int t = numRows * 2 - 2;
        for (int i = 0; i < n; ++i) {
            mat[x] += s[i];
            if (i % t < numRows - 1) {
                ++x;
            } else {
                --x;
            }
        }
        string res;
        for (auto& row : mat) {
            res += row;
        }
        return res;
    }
};
